﻿namespace Graph;

public class DFSCycleDetection
{
    private IGraph G;
    private bool[] visited;
    private int[] pre;

    public bool HasCycle { get; private set; }

    public DFSCycleDetection(IGraph G)
    {
        this.G = G;

        visited = new bool[G.V];
        pre = new int[G.V];
        for (int i = 0; i < pre.Length; i++)
        {
            pre[i] = -1;
        }

        for (int v = 0; v < G.V; v++)
        {
            if (!visited[v])
            {
                DFS(v);
            }
        }
    }

    private void DFS(int v)
    {
        visited[v] = true;

        foreach (int w in G.Adj(v))
        {
            if (!visited[w])
            {
                pre[w] = v;
                DFS(w);
            }
            else
            {
                if (G is IDiGraph)
                {
                    HasCycle = true;
                    return;
                }
                else
                {
                    if (w != pre[v])
                    {
                        HasCycle = true;
                        return;
                    }
                }
            }
        }
    }

    //验证
    static void Main(string[] args)
    {
        //IGraph graph = new AdjLinkList("无向无权图/g4.txt");
        IDiGraph graph = new DiAdjLinkList("有向无权图/无权有环图.txt");
        Console.WriteLine(graph);
        DFSCycleDetection cycleDetection = new(graph);
        Console.WriteLine(cycleDetection.HasCycle);

        Console.Read();



    }
}
